| 翻訳と辞書 |
| friendship graph ： ウィキペディア英語版 |
friendship graph
In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or ''n''-fan) ''F''''n'' is a planar undirected graph with ''2n+1'' vertices and ''3n'' edges.
The friendship graph ''Fn'' can be constructed by joining ''n'' copies of the cycle graph ''C''3 with a common vertex.〔Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic J. Combinatorics, DS6, 1-58, Jan. 3, 2007. ().〕
By construction, the friendship graph ''Fn'' is isomorphic to the windmill graph Wd(3,''n''). It is unit distance with girth 3, diameter 2 and radius 1. The graph ''F''2 is isomorphic to the butterfly graph.
==Friendship theorem==
The friendship theorem of 〔.〕 states that the finite graphs with the property that every two vertices have exactly one neighbor in common are exactly the friendship graphs. Informally, if a group of people has the property that every pair of people has exactly one friend in common, then there must be one person who is a friend to all the others. However, for infinite graphs, there can be many different graphs with the same cardinality that have this property.〔. 〕 A combinatorial proof was given by Mertzios and Unger. Another proof was given by Craig Huneke 〔Huneke, Craig. ("The Friendship Theorem." ) The American Mathematical Monthly 109.2 (2002): 192-94. JSTOR. Mathematical Association of America. Web. 〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「friendship graph」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|